Mi manual de algoritmos/version_maraton_nacional_2008/src/dp/lcs.cpp

   1 #define MAX(a,b) ((a>b)?(a):(b))
   2 int dp[1001][1001];
   3
   4 int lcs(const string &s, const string &t){
   5   int m = s.size(), n = t.size();
   6   if (m == 0 || n == 0) return 0;
   7   for (int i=0; i<=m; ++i)
   8     dp[i][0] = 0;
   9   for (int j=1; j<=n; ++j)
  10     dp[0][j] = 0;
  11   for (int i=0; i<m; ++i)
  12     for (int j=0; j<n; ++j)
  13       if (s[i] == t[j])
  14         dp[i+1][j+1] = dp[i][j]+1;
  15       else
  16         dp[i+1][j+1] = MAX(dp[i+1][j], dp[i][j+1]);
  17   return dp[m][n];
  18 }